// list.cc
//
//     	Routines to manage a singly-linked list of "things".
//
// 	A "DLListElement" is allocated for each item to be put on the
//	list; it is de-allocated when the item is removed. This means
//      we don't need to keep a "next" pointer in every object we
//      want to put on a list.
//
//     	NOTE: Mutual exclusion must be provided by the caller.
//  	If you want a synchronized list, you must use the routines
//	in synchlist.cc.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "dllist.h"
#include "dllist-driver.h"
#include "system.h"

extern int S;
//when F=xxx...x1xxb enable yield test
const int yieldLevel = 3;

//----------------------------------------------------------------------
// DLListElement::DLListElement
// 	Initialize a list element, so it can be added somewhere on a list.
//
//	"itemPtr" is the item to be put on the list.  It can be a pointer
//		to anything.
//	"sortKey" is the priority of the item, if any.
//----------------------------------------------------------------------

DLListElement::DLListElement(void *itemPtr, int sortKey)
{
    item = itemPtr;
    key = sortKey;
    forward = NULL; // assume we'll put it at the begin of the list
    next = NULL;    // assume we'll put it at the end of the list
}

//----------------------------------------------------------------------
// List::List
//	Initialize a list, empty to start with.
//	Elements can now be added to the list.
//----------------------------------------------------------------------

DLList::DLList()
{
    first = last = NULL;
    listLock = new Lock("list lock");
    listEmptyCond = new Condition("list empty");
}

//----------------------------------------------------------------------
// List::~List
//	Prepare a list for deallocation.  If the list still contains any
//	DLListElements, de-allocate them.  However, note that we do *not*
//	de-allocate the "items" on the list -- this module allocates
//	and de-allocates the DLListElements to keep track of each item,
//	but a given item may be on multiple lists, so we can't
//	de-allocate them here.
//----------------------------------------------------------------------

DLList::~DLList()
{
    while (Remove() != NULL)
        ; // delete all the list elements
}

//----------------------------------------------------------------------
// List::Begin
//      Return the iterator of the first element.
//
//      If the list is empty, then return NULL.
//----------------------------------------------------------------------

DLListElement *
DLList::Begin()
{
    return first;
}

//----------------------------------------------------------------------
// List::End
//      Return the iterator of the last element.
//
//      If the list is empty, then return NULL.
//----------------------------------------------------------------------

DLListElement *
DLList::End()
{
    return last;
}

//----------------------------------------------------------------------
// List::Append
//      Append an "item" to the end of the list.
//
//	Allocate a DLListElement to keep track of the item.
//      If the list is empty, then this will be the only element.
//	Otherwise, put it at the end.
//
//	"item" is the thing to put on the list, it can be a pointer to
//		anything.
//----------------------------------------------------------------------

void DLList::Append(void *item)
{
    listLock->Acquire();

    DLListElement *element = new DLListElement(item, 0);

    if (IsEmpty())
    { // list is empty
        first = element;
        last = element;
    }
    else
    { // else put it after last
        element->forward = last;
        last->next = element;
        last = element;
    }

    listEmptyCond->Signal(listLock);
    listLock->Release();
}

//----------------------------------------------------------------------
// List::Prepend
//      Put an "item" on the front of the list.
//
//	Allocate a DLListElement to keep track of the item.
//      If the list is empty, then this will be the only element.
//	Otherwise, put it at the beginning.
//
//	"item" is the thing to put on the list, it can be a pointer to
//		anything.
//----------------------------------------------------------------------

void DLList::Prepend(void *item)
{
    listLock->Acquire();

    DLListElement *element = new DLListElement(item, 0);

    if (IsEmpty())
    { // list is empty
        first = element;
        last = element;
    }
    else
    { // else put it before first
        element->next = first;
        first->forward = element;
        first = element;
    }

    listEmptyCond->Signal(listLock);
    listLock->Release();
}

//----------------------------------------------------------------------
// List::Remove
//      Remove the first "item" from the front of the list.
//
// Returns:
//	Pointer to removed item, NULL if nothing on the list.
//----------------------------------------------------------------------

void *
DLList::Remove()
{
    return SortedRemove(NULL); // Same as SortedRemove, but ignore the key
}

//----------------------------------------------------------------------
// List::Mapcar
//	Apply a function to each item on the list, by walking through
//	the list, one element at a time.
//
//	Unlike LISP, this mapcar does not return anything!
//
//	"func" is the procedure to apply to each element of the list.
//----------------------------------------------------------------------

void DLList::Mapcar(VoidFunctionPtr func)
{
    listLock->Acquire();

    for (DLListElement *ptr = first; ptr != NULL; ptr = ptr->next)
    {
        DEBUG('l', "In mapcar, about to invoke %x(%x)\n", func, ptr->item);
        (*func)((int)ptr->item);
    }

    listLock->Release();
}

//----------------------------------------------------------------------
// List::IsEmpty
//      Returns TRUE if the list is empty (has no items).
//----------------------------------------------------------------------

bool DLList::IsEmpty()
{
    if (first == NULL)
        return TRUE;
    else
        return FALSE;
}

//----------------------------------------------------------------------
// List::SortedInsert
//      Insert an "item" into a list, so that the list elements are
//	sorted in increasing order by "sortKey".
//
//	Allocate a DLListElement to keep track of the item.
//      If the list is empty, then this will be the only element.
//	Otherwise, walk through the list, one element at a time,
//	to find where the new item should be placed.
//
//	"item" is the thing to put on the list, it can be a pointer to
//		anything.
//	"sortKey" is the priority of the item.
//----------------------------------------------------------------------

void DLList::SortedInsert(void *item, int sortKey)
{
    listLock->Acquire();

    DLListElement *element = new DLListElement(item, sortKey);
    DLListElement *ptr; // keep track
    printf("%s:Insert key:%d\n", currentThread->getName(), sortKey);
    if (IsEmpty())
    { // if list is empty, put

        MayBeYield(yieldLevel);

        first = element;
        last = element;
    }
    else if (sortKey < first->key)
    {
        MayBeYield(yieldLevel);
        // item goes on front of list
        element->next = first;
        MayBeYield(yieldLevel);
        first->forward = element;
        MayBeYield(yieldLevel);
        if (S == 1)
        {
            printf("I:%s wanna go to yield.\n", currentThread->getName());
            currentThread->Yield();
        }
        first = element;
    }
    else
    { // look for first elt in list bigger than item
        for (ptr = first; ptr->next != NULL; ptr = ptr->next)
        {
            if (sortKey < ptr->next->key)
            {
                MayBeYield(yieldLevel);

                element->next = ptr->next;
                MayBeYield(yieldLevel);
                if (S == 2)
                {
                    printf("I:%s wanna go to yield.\n", currentThread->getName());
                    currentThread->Yield();
                }
                ptr->next->forward = element;
                MayBeYield(yieldLevel);
                ptr->next = element;
                MayBeYield(yieldLevel);
                element->forward = ptr;
                MayBeYield(yieldLevel);

                listLock->Release();
                return;
            }
        }
        last->next = element; // item goes at end of list
        element->forward = last;
        last = element;
    }

    listEmptyCond->Signal(listLock);
    listLock->Release();
}

//----------------------------------------------------------------------
// List::SortedRemove
//      Remove the first "item" from the front of a sorted list.
//
// Returns:
//	Pointer to removed item, NULL if nothing on the list.
//	Sets *keyPtr to the priority value of the removed item
//	(this is needed by interrupt.cc, for instance).
//
//	"keyPtr" is a pointer to the location in which to store the
//		priority of the removed item.
//----------------------------------------------------------------------

void *
DLList::SortedRemove(int *keyPtr)
{
    listLock->Acquire();
    while (IsEmpty())
    {
        listEmptyCond->Wait(listLock);
    }

    printf("%s start removing.\n", currentThread->getName());
    DLListElement *element = first;
    void *thing;

    if (IsEmpty())
    {
        listLock->Release();
        return NULL;
    }

    thing = first->item;

    MayBeYield(yieldLevel);

    if (first == last)
    { // list had one item, now has none
        MayBeYield(yieldLevel);

        first = NULL;
        last = NULL;
    }
    else
    {
        if (S == 3 || S == 4)
        {
            printf("I:%s wanna go to yield.\n", currentThread->getName());
            currentThread->Yield();
        }
        MayBeYield(yieldLevel);
        //printf("I:%s wanna go to yield.\n",currentThread->getName());
        //currentThread->Yield();
        first = element->next;
    }
    if (keyPtr != NULL)
        *keyPtr = element->key;
    delete element;

    listLock->Release();
    return thing;
}
